class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int len=s.length();
        if(len%2!=0)return false;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == '(') {
                st.push(')');
            } else if (c == '[') {
                st.push(']');
            } else if (c == '{') {
                st.push('}');
            } else {
                if (st.empty() || st.top() != c) {
                    return false;
                }
                st.pop();
            }
        }
        
        return st.empty();
    }
};